#include "Sort.h"
#include "Stack.h"

// 交换函数

static void Swap (int* x , int* y)
{

    int tmp = *x ;

    *x = *y ;

    *y = tmp ;

}

// 比较排序 

// 插入排序

void InsertSort (int* arr , int n)
{

    assert (arr) ;

    for (int i = 0 ; i < n ; i++)
    {

        int end = i ;

        int tmp = arr [end + 1] ;

        while (end >= 0)
        {

            if (arr [end] > tmp)
            {

                arr [end + 1] = arr [end] ;

                end-- ;

            }

            else
            {

                break ;

            }

        }

        arr [end + 1] = tmp ;

    }

}

// 希尔排序

void ShellSort (int* arr , int n)
{

    assert (arr) ;

    int gap = n ;

    while (gap > 1)
    {

        gap = gap / 3 + 1 ;

        for (int i = 0 ; i < n - gap ; i++)
        {

            int end = i ;

            int tmp = arr [end + 1] ;

            // 对每组之间进行插入排序

            while (end >= 0)
            {

                if (arr [end] > tmp)
                {

                    arr [end + 1] = arr [end] ;

                    end-- ;
                }

                else
                {

                    break ;
                    
                }

            }

            arr [end + 1] = tmp ;

        }

    }
    
}

// 直接选择排序

void SelectSort (int* arr , int n)
{

    assert (arr) ;

    int begin = 0 ;

    int end = n - 1 ;

    while (begin < end)
    {

        int mini = begin ;

        int maxi = end ;

        for (int i = begin + 1 ; i <= end ; i++)
        {

            if (arr [i] < arr [mini])
            {

                mini = i ;

            }

            if (arr [i] > arr [maxi])
            {

                maxi = i ;

            }

        }

        // mini begin
        // maxi end

        if (maxi == begin) // 当极值出现在了某一端的时候,交换需要特殊处理
        {

            maxi = mini ;

        }

        Swap (&arr [mini] , &arr [begin]) ;

        Swap (&arr [maxi] , &arr [end]) ;

        begin++ ;

        end-- ;

    }

}

// 堆排序---向下调整算法

static void AdjustDown (int* arr , int parent , int n)
{

    assert (arr) ;

    int child = parent * 2 + 1 ;

    while (child < n)
    {

        // 建大堆: <
        // 建小堆: >

        if (child + 1 < n && arr [child] < arr [child + 1])
        {

            child++ ;

        }

        // 建大堆: > 
        // 建小堆: <

        if (arr [child] > arr [parent])
        {

            Swap (&arr [child] , &arr [parent]) ;

            parent = child ;

            child = parent * 2 + 1 ;

        }

        else
        {

            break ;

        }


    }

}

// 堆排序---排序算法

void HeapSort (int* arr , int n)
{

    assert (arr) ;

    // 升序: 建大堆
    // 降序: 建小堆

    for (int i = (n - 1 - 1) / 2 ; i >= 0 ; i--)
    {

        AdjustDown (arr , i , n) ;

    }

    int end = n - 1 ;

    while (end > 0)
    {

        Swap (&arr [0] , &arr [end]) ;

        AdjustDown (arr , 0 , end) ;
        
        end-- ;

    }

}

// 冒泡排序

void BubbleSort (int* arr , int n)
{

    assert (arr) ;

    int flag = 1 ;

    for (int j = 0 ; j < n ; j++)
    {

        for (int k = 0 ; k < n - j ; k++)
        {

            if (arr [k] > arr [k + 1])
            {

                Swap (&arr [k] , &arr [k + 1]) ;

                flag = 0 ;

            }

        }

        if (flag)
        {

            break ;

        }

    }

}

// 快速排序

// 快速排序---hoare找基准值法

int _QuickSortHoare (int* arr , int left , int right)
{

    assert (arr) ;

    int keyi = left ;

    ++left ; // left从keyi的下一个排数据

    while (left <= right)
    {

        // right: 从右往左走,找比基准值小的

        while (left <= right && arr [right] > arr [keyi])
        {

            right-- ;

        }

        // left: 从左往右走,找比基准值大的

        while (left <= right && arr [left] < arr [keyi])
        {

            left++ ;

        }

        // 上面两条的判断条件不能等于,因为如果有特殊的数组(所有值一样),就会进入循环运算,最坏的情况就会变成O(n^2)

        // right left

        if  (left <= right)
        {

            Swap (&arr [left++] , &arr [right--]) ;

        }

    }

    Swap (&arr [keyi] , &arr [right]) ;

    return right ;
}

// 快速排序---挖坑找基准值法
// 用得比较少
// 因为该方法不能处理重复的数据,会死循环
// 如果将内层循环改成=号,就不会死循环,但是递归次数可能就会变成O(n^2)

int _QuickSortMine (int* arr , int left , int right)
{

    assert (arr) ;

    int hole = left ;

    int key = arr [hole] ;

    left++ ;

    while (left < right)
    {

        while (left < right && arr [right] > key)
        {

            right-- ;

        }

        arr [hole] = arr [right] ;

        hole = right ;

        while (left < right && arr [left] < key)
        {

            left++ ;

        }

        arr [hole] = arr [left] ;

        hole = left ;

    }
 
    arr [hole] = key ;

    return hole ;

}

// 快速排序---lomuto前后指针寻找基准值法
// 创建两个指针prev cur ,cur从左往右找比基准值要小的数据,prev和cur交换

// cur探路,找比基准值小的数据: 
// (1).cur找到了比基准值小的数据: ++prev,prev和cur的数据交换,cur++ ;
// (2).cur未找到比基准值小的数据: cur++ ;

int _QuickSortLomuto (int* arr , int left , int right)
{

    assert (arr) ;

    int keyi = left ;

    int prev = left , cur = prev + 1 ;

    while (cur <= right)
    {

        if (arr [cur] < arr [keyi] && ++prev != cur)
        {

            Swap (&arr [prev] , &arr [cur]) ;

        }

        cur++ ;

    }

    Swap (&arr [keyi] , &arr [prev]) ;

    return prev ;
    
}

// 快速排序---排序算法

void QuickSortA (int* arr , int left , int right)
{

    assert (arr) ;

    if (left >= right)
    {

        return ;

    }

    // 找基准值i

    // int keyi = _QuickSortHoare (arr , left , right) ;

    // int keyi = _QuickSortMine (arr , left , right) ;
    
    int keyi = _QuickSortLomuto (arr , left , right) ;

    // left keyi right
    // 左序列 [left , keyi - 1] 右序列

    QuickSortA (arr , left , keyi - 1) ;

    QuickSortA (arr , keyi + 1 , right) ;

}

// 快速排序---进入函数
// 为了实现接口统一,封装了一层函数
// 外面用了转移表

void QuickSort (int* arr , int n)
{

    int left = 0 ;

    int right = n - 1 ;

    QuickSortA (arr , left , right) ;

}

// 非递归版本的快速排序---栈结构实现

// 非递归版本---排序算法

void QuicSortNoR (int* arr , int left , int right)
{

    assert (arr) ;

    ST st ;

    SInit (&st) ;

    SPush (&st , left) ;

    SPush (&st , right) ;

    // 这里使用了lomuto双指针找基准值法

    while (!SEmpty (&st))
    {

        // 取栈顶两次
        
        int end = STop (&st) ;

        SPop (&st) ;

        int begin = STop (&st) ;

        SPop (&st) ;

        // [begin , end]找基准值

        int keyi = begin ;
        
        int prev = begin , cur = prev + 1 ;

        while (cur <= end)
        {

            if (arr [cur] < arr [keyi] && ++prev != cur)
            {

                Swap (&arr [prev] , &arr [cur]) ;

            }

            cur++ ;
            
        }

        Swap (&arr [keyi] , &arr [prev]) ;

        keyi = prev ;

        // begin keyi end
        // 左序列: [begin , keyi - 1] , 右序列: [keyi + 1 , end]

        if (keyi + 1 < end)
        {

            SPush (&st , keyi + 1) ;

            SPush (&st , end) ;

        }

        if (keyi - 1 > begin)
        {

            SPush (&st , begin) ;

            SPush (&st , keyi - 1) ;

        }

    }

    SDestory (&st) ;

}

// 非递归版本---进入函数

void QuickSortNoR (int* arr , int n)
{

    int left = 0 ;

    int right = n - 1 ;

    QuicSortNoR (arr , left , right) ;

}

// 归并排序

// 归并排序---排序算法

void _MergeSort (int* arr , int left , int right , int* tmp)
{

    if (left >= right)
    {

        return ;

    }

    // [left , right]
    // (left + right) / 2

    int mid = left / 2 + right / 2 ;

    // 根据mid划分左右序列: [left , mid] [mid + 1 , right]

    _MergeSort (arr , left , mid , tmp) ;

    _MergeSort (arr , mid + 1 , right , tmp) ;

    // 合并两个有序的数列

    int begin1 = left , end1 = mid ;

    int begin2 = mid + 1 , end2 = right ;

    int index = begin1 ;

    // [begin1 , end1] [begin2 , end2]

    while (begin1 <= end1 && begin2 <= end2)
    {

        if (arr [begin1] < arr [begin2])
        {

            tmp [index++] = arr[begin1++] ;
            
        }

        else
        {

            tmp [index++] = arr [begin2++] ;

        }

    }

    while (begin1 <= end1)
    {

        tmp [index++] = arr [begin1++] ;
    }

    while (begin2 <= end2)
    {

        tmp [index++] = arr [begin2++] ;

    }

    // tmp中有序的数组导入到原数组
    // [left , right]

    for (int i = left ; i <= right ; i++)
    {

        arr [i] = tmp [i] ;

    }

}

// 归并排序---进入函数

void MergeSort (int* arr , int n)
{

    int* tmp = (int*) malloc (sizeof (int) * n) ;

    int left = 0 ;

    int right = n - 1 ;
    
    _MergeSort (arr , left , right , tmp) ;

    free (tmp) ;

    tmp = NULL ;

}

// 非比较排序

// 计数排序

void CountSort (int* arr , int n)
{

    // 找最大和最小值
    
    int max = arr [0] , min = arr [0] ;

    for (int i = 0 ; i < n ; i++)
    {

        if (arr [i] < min)
        {

            min = arr [i] ;

        }

        if (arr [i] > max)
        {

            max = arr [i] ;

        }
        
    }

    // max - min + 1 确定count数组的大小

    int range = max - min + 1 ;

    int* count = (int*) malloc (sizeof (int) * range) ;

    if (count == NULL)
    {

        perror ("malloc fail!") ;

        exit (1) ;

    }

    // 初始化用calloc

    memset (count , 0 , sizeof (int) * range) ; // 如果这里没有全部初始化为0的话,就会造成arr越界访问

    for (int i = 0 ; i < n ; i++)
    {

        count [arr [i] - min]++ ;

    }

    // 将count数组还原到原数组中,使其有序

    int index = 0 ;

    for (int i = 0 ; i < range ; i++)
    {

        while (count [i]--)
        {

            arr [index++] = i + min ;

        }   

    } 

    free (count) ;

    count = NULL ;

}